package q454_fourSumCount;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    此题可能比较难以想到hash表的解决方式，但是却是一道非常标准的hash题
    首先我们考虑最简单的方式 暴力循环四个数组 直接找出所有答案 其复杂度达到on4
    显然是不能够接受的 但是我们可以通过排序后进行减枝的方法 并且在一些数组可以使用二分查找来减少循环次数
    但是最优解仍然是使用hash表
    首先考虑我们如何使用 n1 + n2 + n3 + n4 = 0 这个等式可以转换为 n1 = - (n2 + n3 + n4) , n1 + n2 = -(n3 + n4)。。
    如果我们使用第一个，也就是hash存入n1数值，然后在后三个的循环中寻找是否有对应的key 仍然达到了on3的复杂度
    所以要用对半分的方法 将n1 + n2捆绑 然后捆绑剩下两个 就能达到on2的复杂度
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                map.put(-(num1 + num2), map.getOrDefault(-(num1 + num2), 0) + 1);
            }
        }
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                ans += map.getOrDefault(num3 + num4, 0);
            }
        }
        return ans;
    }
}
